package Array.easy;

import java.util.Arrays;

/**
 * 1. 问题描述
 *      求出数组种的三个数的最大乘积（不一定连续）
 * 2. 算法分析
 *      1. 排序法
 *          先对无序数组进行升序排序，然后取得最大值的情况只用两种
 *          两个最大的负数和最大正数或者三个最大正数
 *          该算法的时间复杂度完全取决于排序算法 jdk底层的排序算法
 *          是优化的快速快速排序，平均时间复杂度为O(logn)
 *      2. 穷举法
 *         实现简单，思路明了，时间复杂度非常高O(n^2)
 *
 *      3. 比较法 (推荐算法)
 *          我们如何确定一个数组种的最小值和次最小值，最大值和次最大值和次次最大值
 *          实际上画一个数轴就非常好理解了，在一次线性扫面的过程中找到上述所有，时间
 *          复杂度为O(n)
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 三个数的最大乘积 {
    public static void main(String[] args) {
        int[] nums = {-5,-3,2,1,4};
        System.out.println(maxProduct2(nums));
    }

    // 排序
    public static int maxProduct(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        return Math.max(nums[0]*nums[1]*nums[len-1],nums[len-1]*nums[len-2]*nums[len-3]);
    }

    // 不需要排序，只需要一次线性扫描即可
    public static int maxProduct2(int[] nums) {
        int min1 = Integer.MAX_VALUE; int min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE; int max2 = Integer.MIN_VALUE; int max3 = Integer.MIN_VALUE;
        for(int item : nums) {
            // 确定 min1  min2
            if(item <= min1) {
                min2 = min1;
                min1 = item;
            } else if (item < min2) {
                min2 = item;
            }
            if (item >= max1) {
                max3 = max2;
                max2 = max1;
                max1 = item;
            } else if (item >= max2) {
                max3 = max2;
                max2 = item;
            } else if (item >= max3) {
                max3 = item;
            }
        }
        return Math.max(min1*min2*max1,max1*max2*max3);
    }
}
